#ifndef DAG_H
#define DAG_H
struct DAG
{
    size_t m;
    int *heads;
    size_t *nex;
    size_t *to;
    size_t ecnt;
    int *rheads;
    size_t *rnex;
    size_t *rto;
    size_t recnt;
    size_t *in_degree;
    size_t *out_degree;
    DAG(size_t m, const std::vector<std::vector<size_t>> &pre_ids) : m(m)
    {
        heads = new int[m];
        rheads = new int[m];
        size_t sum = 0;
        for (size_t i = 0; i < pre_ids.size(); i++)
        {
            heads[i] = -1;
            rheads[i] = -1;
            sum += pre_ids[i].size();
        }
        nex = new size_t[sum];
        rnex = new size_t[sum];
        to = new size_t[sum];
        rto = new size_t[sum];
        in_degree = new size_t[m];
        out_degree = new size_t[m];
        recnt = 0;
        ecnt = 0;
        for (int i = 0; i < pre_ids.size(); i++)
        {
            for (int j = 0; j < pre_ids[i].size(); j++)
            {
                nex[ecnt] = heads[pre_ids[i][j]];
                rnex[recnt] = rheads[i];
                to[ecnt] = i;
                rto[recnt] = pre_ids[i][j];
                heads[pre_ids[i][j]] = ecnt++;
                rheads[i] = recnt++;
                out_degree[pre_ids[i][j]]++;
            }
        }
    }
    ~DAG()
    {
        delete[] in_degree;
        delete[] out_degree;
        delete[] heads;
        delete[] rheads;
        delete[] nex;
        delete[] rnex;
        delete[] to;
        delete[] rto;
    }
    // 禁止拷贝构造和赋值（防止浅拷贝）
    DAG(const DAG &) = delete;
    DAG &operator=(const DAG &) = delete;

    // 允许移动构造和赋值（可选，提升性能）
    DAG(DAG &&other)
        : m(other.m),
          heads(other.heads),
          nex(other.nex),
          to(other.to),
          ecnt(other.ecnt),
          rheads(other.rheads),
          rnex(other.rnex),
          rto(other.rto),
          recnt(other.recnt),
          in_degree(other.in_degree),
          out_degree(other.out_degree)
    {
        // 转移资源后，将 other 置空
        other.heads = nullptr;
        other.nex = nullptr;
        other.to = nullptr;
        other.rheads = nullptr;
        other.rnex = nullptr;
        other.rto = nullptr;
        other.in_degree = nullptr;
        other.out_degree = nullptr;
    }

    DAG &operator=(DAG &&other)
    {
        if (this != &other)
        {
            // 释放当前资源
            delete[] heads;
            delete[] nex;
            delete[] to;
            delete[] rheads;
            delete[] rnex;
            delete[] rto;
            delete[] in_degree;
            delete[] out_degree;

            // 转移资源
            m = other.m;
            heads = other.heads;
            nex = other.nex;
            to = other.to;
            ecnt = other.ecnt;
            rheads = other.rheads;
            rnex = other.rnex;
            rto = other.rto;
            recnt = other.recnt;
            in_degree = other.in_degree;
            out_degree = other.out_degree;

            // 置空
            other.heads = nullptr;
            other.nex = nullptr;
            other.to = nullptr;
            other.rheads = nullptr;
            other.rnex = nullptr;
            other.rto = nullptr;
            other.in_degree = nullptr;
            other.out_degree = nullptr;
        }
        return *this;
    }
};

#endif